package a_doubleWrite;

import java.util.Arrays;

/**
 * 215. 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * @author: luolidong
 * @create: 2021-07-19 16:51
 * @version: 1.0
 */
public class L215 {
    public int findKthLargest(int[] nums, int k) {
        //快排，降序，第k大对应k-1索引
        return quickSort(nums, 0, nums.length - 1, k - 1);
    }

    public int quickSort(int[] nums, int left, int right, int k) {
        int mid = partition(nums, left, right);

        if (mid == k)
            return nums[mid];
        else if (mid > k)
            return quickSort(nums, left, mid - 1, k);
        else
            return quickSort(nums, mid + 1, right, k);
    }

    private int partition(int[] nums, int left, int right) {
        int p = nums[left];//基准值
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && nums[r] < p) {
                r--;
            }
//            /* nums[l] >= p 需要=,因为l从基准值开始，需要跳过 */
            while (l < r && nums[l] >= p) {
                l++;
            }
            if (l < r) {
                swap(nums, l, r);
            }
        }
        swap(nums, left, l);
        return l;//基准值位置
    }

    public void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 6, 3, 8, 3, 2, 5, 5, 7, 9, 8};
        L215 l215 = new L215();
        int kthLargest = l215.findKthLargest(nums, 4);
        System.out.println("Arrays.toString(nums) = " + Arrays.toString(nums));
        System.out.println("kthLargest = " + kthLargest);


    }
}
